| class WTD_DIGRAPH_ALG{NTP<$STR,WT<$NUMBER{WT},GTP<$LBLD_DIGRAPH{NTP,WT,WT}} |
|---|
| **** |
___NTP, --_Node_type ___WT<$NUMBER{WT}, --_Weight_type ___GTP<$LBLD_DIGRAPH{NTP,WT,WT}_--_Labelled_Graph_type ___Largely_translated_from_the_LEDA_library _ Usage: ___It_is_simplest_to_use_these_algorithms_by_including ___them_using_WTD_DIGRAPH_INCL._For_instance,_see_WTD_DIGRAPH{STR,FLT},_ ___You_can_also_directly_call_thes_routines__See_TEST_WTD_DIGRAPH ___If_you_have_to_use_this_class_directly,_keep_the_parameters_straight! |
| COMPARE{_} |
| shared debug: BOOL := false; |
|---|
| shared debug: BOOL := false; |
|---|
| bellman_ford(g:GTP,s:NTP,out d:MAP{NTP,WT},out p:MAP{NTP,NTP}): BOOL |
|---|
| **** | Computes the source shortest paths from "s" using a queue and breadth first search. On return, "d" holds a mapping from nodes to their distances for "src" and "pred" holds a mapping from each node to its parent node in the shortest paths tree. Returns true if no negative cycle was found
_ _ Implementation: Note that bellman_ford works even in cyclic graphs, provided there is no cycle with negative weight (in which case the min weight to any of the nodes in the cycle can be arbitrarily decreased) If such a negative weight cycle is found, the routine quits and returns false - it can therefore also be used as a reliable detector of negative cycles. _ |
| dijkstra(g:GTP,s:NTP,out dist:MAP{NTP,WT},out |
|---|
| **** | Please see the comment at WTD_DIGRAPH_ALG{_,_,_,_}::dijkstra Computes single source shortest paths from "src" for a non-negative graph i.e. one without negative cycles. Returns the distance from "src" to all other nodes in "dist" and the predecessor of each node of "g" in the shortest paths tree in "pred"
_ Usage: ___See_bellman_ford |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| maxval: WT |
|---|
| zero: WT |
|---|
| max_weight_path_node!(once g: GTP,once src,once sink: NTP): NTP |
|---|
| **** | Computes the maximum node-weight path from "src" to "sink" in the graph "g", returning a list of nodes in that maximum weight path that starts with "src" and ends with "sink" Fully considered only for DAGs: May have problems with other types of graphs |
| deb(s: STR): BOOL |
|---|
| deb2(s: STR) |
|---|
| node_str(n: NTP): STR |
|---|
| str(e: $OB): STR |
|---|